package com.zxy.leetcode._00000_00099._00090_00099;

import com.zxy.leetcode.common.ListNode;
import com.zxy.leetcode.common.ListNodeHelper;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 *
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 标签：链表
 */
public class Test00092 {

    public static void main(String[] args) {
        Test00092 test = new Test00092();
        ListNode head = ListNodeHelper.build(5);
        head = test.reverseBetween(head, 2, 4);
        ListNodeHelper.print(head);

        head = ListNodeHelper.build(5);
        head = test.reverseBetween(head, 3, 5);
        ListNodeHelper.print(head);

        head = ListNodeHelper.build(5);
        head = test.reverseBetween(head, 1, 2);
        ListNodeHelper.print(head);

        head = ListNodeHelper.build(5);
        head = test.reverseBetween(head, 1, 5);
        ListNodeHelper.print(head);
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }

        ListNode tmpNode = new ListNode(0, head);
        ListNode pLeft = tmpNode;
        for (int i=1; i<m; i++) {
            pLeft = pLeft.next;
        }
        if (pLeft.next == null) {
            return head;
        }

        ListNode pLeftNext = pLeft.next;
        ListNode p1 = pLeft.next;
        ListNode p2 = p1.next;
        for (int i=m; i<n; i++) {
            ListNode p3 = p2.next;
            p2.next = p1;

            p1 = p2;
            p2 = p3;
        }
        pLeft.next = p1;
        pLeftNext.next = p2;

        return tmpNode.next;
    }

}
